googologywikiaorg-20200223-history
Talk:Transcendental integer
anyone have an idea why 2^1000 was chosen? WikiRigbyDude (talk) 14:17, August 26, 2014 (UTC) :Is \(\Sigma(2^{1000})\) a transcedental integer? Wythagoras (talk) 10:03, September 6, 2014 (UTC) :I think so. With \(2^{1000}\) states we can quite surely compute functions beyond the scope of ZFC. But I cannot prove that this is the case. LittlePeng9 (talk) 10:42, September 6, 2014 (UTC) ::While to be sure we would have to program a TM that searched through all ZFC proofs, it is inconceivable that this could not be done in fewer than 2^1000 states. (I would guess fewer than 10000 is possible.) Deedlit11 (talk) 10:57, September 6, 2014 (UTC) ::We can't prove that a k-state BB can't be proven to be halt in just k symbols? Wythagoras (talk) 11:41, September 6, 2014 (UTC) :::No, because given TM we don't know a priori that it's a busy beaver. LittlePeng9 (talk) 12:48, September 6, 2014 (UTC) :::Did you mean k states rather than k symbols? In that case, the answer is yes, we can. Let's say we have a TM that runs through all ZFC proofs of n steps or less that uses m states. We can use p states to output a number of size \(\Sigma(p)\), so we can use m + p states to check all ZFC proofs of size \(\Sigma(p)\) states or less. For sufficiently large p, we will have \(\Sigma(p) > m+p\), so for sufficiently large k we can verify that a k-state BB halts using fewer than k states (assuming the halting is provable in ZFC). Deedlit11 (talk) 00:53, September 7, 2014 (UTC) ::::How can a ZFC proof have "k states"? LittlePeng9 (talk) 06:15, September 7, 2014 (UTC) Are transcendental integers well-defined? Definition 1. For turing machine \(M\), let \(T(M)\) be the execution time of \(M\). Proposition 2. For all integers \(n\), there exists a turing machine \(M\) such that \(T(M) > n\). Proof. Consider a turing machine \(M\) such that: # \(Q = {q_0, q_1, q_2, ..., q_n, q_{n+1}}\) where \(Q\) is the set of states. # \(q_0\) is the initial state. # \(q_{n+1}\) is the halting state. # For all \(k < n+1\), \(q_k\) will transit to \(q_{k+1}\) regardless of the tape content. \(M\) will run \(n+1\) steps and halt.∎ Proposition 3. Proposition 2. is provable within \(ZFC\) using at most \(2^{1000}\) symbols. Sketch of a proof. Write down the proof of proposition 2. in a formal language and count the symbols of the proof.∎ Proposition 4. Any integers are not transcendental. Proof. Assume \(n\) is a transcendental integer. By proposition 2., there exists a TM \(M\) such that \(T(M) > n\). By proposition 3. and the definition of transcendental integers, \(n ≥ T(M)\) which is a contradiction.∎Vyv03354 (talk) 03:18, October 15, 2017 (UTC) :Here is the flaw in this reasoning: Even though ZFC proves "for every \(n\) there is a TM halting after more than \(n\) steps" in less than \(2^{1000}\) symbols, it doesn't follow that for every single \(n\) ZFC proves "there is a TM halting after more than \(n\) steps". The reason this doesn't go through immediately is that the statement "there is a TM halting after more than \(n\) steps" for some particular \(n\) needs to include a description of this particular \(n\) in the statement, which can easily take us above \(2^{1000}\) symbols if \(n\) is large. LittlePeng9 (talk) 08:07, October 15, 2017 (UTC) ::The definition of transcendental integers does not require a proof for the statement "there is a TM halting after more than \(n\) steps". It only requires "\(M\) halts". The length limit does not apply to the description of \(n\). ::But I understand your point. Even if ZFC proves "for every \(n\) there is a TM \(M\) halting after more than \(n\) steps" in less than \(2^{1000}\) symbols, it doesn't follow that for every single \(n\) there is a TM \(M\) and ZFC proves that "\(M\) halts" in less than \(2^{1000}\) symbols and \(M\) halts after more than \(n\) steps, because the latter requires a description of a particular \(M\). In my example, it is almost the same as the description of \(n\). Correct? Vyv03354 (talk) 10:54, October 15, 2017 (UTC) :::Exactly, that's the idea. LittlePeng9 (talk) 11:12, October 15, 2017 (UTC) :::Flaw in flaw: ZFC proves "for all n, there's a TM halting only after more than n steps", giving infinitely many special cases. Choose the one with n=2^E3, and success. Also, a flaw in the name: \(\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{A}\Rightarrow\mathbb{Z}\subset\mathbb{A}\). 15:16, March 13, 2018 (UTC)